#include "nickers.h"
#include <map>
#include <string.h>
#include <stdlib.h>

#include "nickers.h"

#ifndef VAR
#define VAR(i,v) __typeof((v))i=(v)
#define FOREACH(i,v) for(VAR(i,(v).begin());i!=(v).end();i++)
#endif

using namespace std;

struct sNuc
{
	int front, end;
	int len;
	std::list<std::string> list;
};

// ------------------------------------------------
int *save_next = NULL;
int *save_len = NULL;
int save_best=-1;
vector<string>	save_input;

void displayBestSeq(int **graph)
{
	printf("BEST: %d\n", save_best);
	for(unsigned int i=0;i<save_input.size();i++) printf("%2d ", i); printf("\n");
	for(unsigned int i=0;i<save_input.size();i++) printf("---"); printf("\n");
	for(unsigned int i=0;i<save_input.size();i++) printf("%2d ", save_next[i]); printf("\n");
	for(unsigned int i=0;i<save_input.size();i++) printf("%2d ", save_len[i]); printf("\n");

	int adr = save_best;
	int p = graph[adr][save_next[adr]];
	printf("%s\n", save_input[adr].c_str());
	adr = save_next[adr];
	while (adr!=save_next[adr])
	{
		for (int i=0;i<p;i++) printf(" ");
		printf("%s\n", save_input[adr].c_str());
		p += graph[adr][save_next[adr]];
		adr = save_next[adr];
	}
}

void clearBest()
{
	if (save_next) delete[] save_next;
	if (save_len) delete[] save_len;
	save_next = NULL;
	save_best = -1;
	save_input.clear();
}
// --------------------------------------------------

int getLengthFrom(int s, int* n)
{
	int l = 1;
	while (s!=n[s])
	{
		s=n[s];
		l++;
	}
	return l;
}

int getLastFrom(int s, int* n)
{
	s = n[s];
	while (n[s] != s)
		s = n[s];
	return (s);
}


/**
 * Pobierz losowy element z listy.
 * @param a lista intów
 * @return wylosowany element
 */
int getRandom(list<int> a)
{
	if (a.empty())
		return -1;

	int s = rand() % a.size();
	FOREACH(i,a)
	{
		if (s <= 0)
			return (*i);
		s--;
	}

	// should not be here
	return -1;
}

int getRandomBetterAfter(list<int> a, int *next, bool *used, int ** graph, int n)
{
	if (a.empty())
		return -1;

	int b, b_min, b_cnt;

	b = -1;
	b_min = 0;
	b_cnt = n+1;

	FOREACH(i,a)
	{
		int last = getLastFrom(*i, next);
		int min=10, cnt=0;

		for (int j=0; j<n; j++)
		{
			if (!used[j] && *i!=j)
			{
				if (graph[last][j] < min)
				{
					min = graph[last][j];
					cnt = 0;
				}
				if (graph[last][j] == min)
					cnt++;
			}
		}

		if ( (cnt>0) // znaleziono cos...
		&& ((min>b_min) || (min==b_min && cnt<b_cnt)) ) //...i to cos jest w gorszej sytuacji - albo dalej, albo mniej
		{
			b_min = min;
			b_cnt = cnt;
			b = *i;
		}
	}

	return b;
}

/**
 * algo's main function
 */
int mgreedy(vector<string> input, int **graph, int max, int draw_if)
{
	//if (draw_if==0)printf("MAX: %d  CNT: %d\n", max, input.size());
	vector<sNuc> all;
	bool *used;
	int *next, *len, elements;
	sNuc n;
	int count = input.size();
	elements = count;

	used = new bool[input.size()];
	next = new int[input.size()];
	len = new int[input.size()];
	memset(used, 0, sizeof(*used) * input.size());

	int cnt = 0;
	FOREACH(i,input)
	{
		//printf(">> %2d] %s\n", cnt, (*i).c_str());
		cnt++;
	}

	// nastepny dla niego to on sam - na poczatku
	for (int i = 0; i < count; i++)
	{
		next[i] = i;
		len[i] = input[i].length();
	}

	// liczba powtorzen - maksymalna
	for (int conn = input.size() * 2; conn > 0; conn--)
	{
		int random = rand() % (elements);
		int a_pos = 0;

		// znajdz element - pomijaj bedace czescia innych
		while (a_pos < count && used[a_pos] == true)
			a_pos++;

		while (random > 0 && a_pos < count)
		{
			a_pos++;
			if (used[a_pos] == false)
				random--;
		}

		if (a_pos >= count)
			break;

		int b_pos = 0;
		bool before = findBestElement(a_pos, graph, used, next, b_pos, count, len, max);

		// printf(" < %2d : %2d == %3d > \n", a_pos, b_pos, before ? graph[getLastFrom(b_pos,next)][a_pos] : graph[getLastFrom(a_pos,next)][b_pos]);

		if (b_pos < 0 || b_pos == a_pos)
			continue;

		// jeden element mniej
		elements--;

		///for (int xi=0; xi<count; xi++) printf("[%d]", len[xi]); printf("\n");

		if (before)
		{
			int last = getLastFrom(b_pos, next);
			next[last] = a_pos;
			used[a_pos] = true;
			len[b_pos] += len[a_pos] - 10 + graph[last][a_pos];
			/// printf(" $$ %d %d %d\n", len[b_pos], len[a_pos], graph[last][a_pos]);
		}
		else
		{
			int last = getLastFrom(a_pos, next);
			next[last] = b_pos;
			used[b_pos] = true;
			len[a_pos] += len[b_pos] - 10 + graph[last][b_pos];
			/// printf(" $$ %d %d %d\n", len[a_pos], len[b_pos], graph[last][b_pos]);
		}
	}

	int mmax=0;
	int adr=0;

	list<int>	other_parts;
	//printf("left : %d\n", elements);
	for (int xi = 0; xi < count; xi++)
	{
		if (!used[xi]) {

			other_parts.push_back(xi);

			int cnt = 1;
			int p = xi;
			while (p!=next[p])
			{
				cnt++;
				p = next[p];
			}
			if (mmax<cnt)
			{
				mmax=cnt;
				adr = xi;
			}
		}
		//if (mmax<len[xi]) mmax=len[xi];
	}

	other_parts.remove(adr);
	mmax = tryToMerge(adr, other_parts, used, next, len, graph, max);


	adr = 0;
	for (unsigned int xi = 0; xi < input.size(); xi++)
		if (len[adr]<len[xi])
			adr = xi;

	/**
	 * save best sequence
	 */
	if (draw_if<mmax)
	{
		clearBest();
		save_input = input;
		save_next = new int[input.size()];
		save_len = new int[input.size()];
		memcpy(save_len, len, sizeof(len[0])*input.size());
		memcpy(save_next, next, sizeof(next[0])*input.size());
		save_best = adr;
	}
	/**
	 * display sequence
	if (draw_if<mmax)
	{
		int p = graph[adr][next[adr]];
		printf("%s\n", input[adr].c_str());
		adr = next[adr];
		while (adr!=next[adr])
		{
			for (int i=0;i<p;i++) printf(" ");
			printf("%s\n", input[adr].c_str());
			p += graph[adr][next[adr]];
			adr = next[adr];
		}
	}
	//printf("\n[[[ %d / %d]]]\n", mmax, max);fflush(NULL);

	*/

//	printf("L %d\n", len[adr]);

	delete[] used;
	delete[] next;
	delete[] len;

	return mmax;
}

bool findBestElement(int a_pos, int** graph, bool *used, int *next, int &b_pos, int len, int *lengths, int max)
{
	list<int> alla, allb;
	int bef = 9, aft = 9;

	//int last = getLastFrom(a_pos, next);

	// dodawane po 'a_pos'
	/*
	for (int i = 0; i < len; i++)
	{
		// juz uzyte
		if (used[i] || a_pos == i)
			continue;

		if ((graph[last][i] < aft)
		&& ((lengths[a_pos] + lengths[i] - 10 + graph[last][i]) < max))
		{
			alla.clear();
			aft = graph[last][i];
		}

		if ((graph[last][i] == aft)
		&& ((lengths[a_pos] + lengths[i] - 10 + graph[last][i]) < max))
			alla.push_back(i);
	}
	*/

	alla = findBestAfter(a_pos, next, used, graph, lengths, len, max, aft);

	// dodawane przed 'a_pos'
	for (int i = 0; i < len; i++)
	{
		// uzyty - a liczymy tylko dla poczatkowych
		if (used[i] || i == a_pos)
			continue;

		int last = getLastFrom(i, next);

		if ((graph[last][a_pos] < bef)
		&& ((lengths[i] + lengths[a_pos] - 10 + graph[last][a_pos]) < max))
		{
			bef = graph[last][a_pos];
			allb.clear();
		}

		if ((graph[last][a_pos] == bef)
		&& ((lengths[i] + lengths[a_pos] - 10 + graph[last][a_pos]) < max))
			allb.push_back(i);
	}

	if (aft < bef)
	{
		//b_pos = getRandom(alla);
		b_pos = getRandomBetterAfter(alla, next, used, graph, len);
		return false;
	}

	b_pos = getRandom(allb);
	return true;
}

// --------------------------------------------------------------------
// -- próba łączenia
// --------------------------------------------------------------------
int tryToMerge(int best, list<int> others, bool *used, int *next, int *lengths, int **graph, int max)
{
	if (others.empty())
		return getLengthFrom(best, next);

	int last = getLastFrom(best, next);

	list<int> sorted;
	while (!others.empty())
	{
		int min = others.front();
		FOREACH(i,others)
			if (graph[last][*i] < graph[last][min])
				min = *i;
		sorted.push_back(min);
		others.remove(min);
	}
	others = sorted;

	list<int> to_remove;

	// najpierw całości
	FOREACH(i,others)
	{
		int len_after = lengths[best]+lengths[*i]-10 + graph[last][*i];
		int len_before = lengths[best]+lengths[*i]-10 + graph[getLastFrom(*i,next)][best];

		if (len_after<=len_before && len_after <= max)
		{
			lengths[best] += lengths[*i] -10 + graph[last][*i];

			next[last] = *i;
			used[*i] = true;
			last = getLastFrom(last, next);
		}
		else if (len_before <= max)
		{
			int new_last = getLastFrom(*i,next);
			lengths[*i] += lengths[best] - 10 + graph[new_last][best];
			next[new_last] = best;
			used[best] = true;
			best = *i;
			to_remove.push_back(best);
		}
	}

	FOREACH(i,to_remove)
		others.remove(*i);

	// teraz kawalki
	// uwaga - niektóre podsekwencje mogly juz byc dołączone w kroku poprzednim
	bool no_more = false;

	while (!no_more)
	{
		no_more = true;

		FOREACH(i,others)
		{
			int p = *i;
			while (!used[p] && lengths[best]+graph[last][p] <= max)
			{
				// przesun element z poczatku jednej listy na koniec drugiej
				*i = next[p];
				next[last] = p;
				next[p] = p;

				lengths[best] += graph[last][p];

				// ustaw markery
				used[p] = true;
				used[*i] = false;
				last = p;
				p = *i;

				no_more = false;
			}
		}
	}

	return getLengthFrom(best, next);
}

list<int> findBestAfter(int a_pos, int *next, bool *used, int **graph, int *lengths, int len, int max, int &aft)
{
	list<int> alla;
	int last = getLastFrom(a_pos, next);

	for (int i = 0; i < len; i++)
	{
		// juz uzyte
		if (used[i] || a_pos == i)
			continue;

		if ((graph[last][i] < aft)
		&& ((lengths[a_pos] + lengths[i] - 10 + graph[last][i]) < max))
		{
			alla.clear();
			aft = graph[last][i];
		}

		if ((graph[last][i] == aft)
		&& ((lengths[a_pos] + lengths[i] - 10 + graph[last][i]) < max))
			alla.push_back(i);
	}

	return alla;
}
